package 回溯;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 目标和494.java
 * @createTime 2022年10月25日 20:13:00
 */
public class 目标和494 {
	int count = 0;

	public int findTargetSumWays(int[] nums, int target) {
		backTrace(nums,target,0,0);
		return count;
	}

	public void backTrace(int[] nums, int target, int numIndex, int curSum) {
		//结果判断: 到结尾了，并且结果和刚好相等
		if (numIndex == nums.length) {
			if (curSum == target) {
				count++;
			}
			return;
		}

		//循环：因为是一个一个的数递归调用的，等同于循环
		// 做选择，只有两种选择
		backTrace(nums, target, numIndex + 1, curSum - nums[numIndex]);
		backTrace(nums, target, numIndex + 1, curSum + nums[numIndex]);

	}
}
